//
// Created by wangxiaodong on 2018/1/3.
//

#ifndef MERGESORT_MERGESORT_H
#define MERGESORT_MERGESORT_H

#include <ostream>

#include "InsertionSort.h"

using namespace std;

namespace MergeSort {

    /**
     * 进行归并
     * @tparam T
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    template <typename T>
    void __merge(T arr[],int l,int mid,int r){
        // 声明临时空间
        T temp[r - l + 1];

        // 拷贝数组
        for (int i = l; i <= r; ++i)
            temp[i - l] = arr[i];


        // 进行排序
        int leftIndex = l;
        int rightIndex = mid + 1;


        for (int tarIndex = l; tarIndex <= r; ++tarIndex) {
            if(rightIndex > r){
                arr[tarIndex] = temp[leftIndex - l];
                leftIndex ++;
            } else if (leftIndex > mid){
                arr[tarIndex] = temp[rightIndex - l];
                rightIndex ++;
            } else if (temp[leftIndex - l] > temp[rightIndex - l]){
                arr[tarIndex] = temp[rightIndex - l];
                rightIndex ++;
            }else{
                arr[tarIndex] = temp[leftIndex - l];
                leftIndex ++;
            }
        }
    }

    /**
     * 对 [l,r]区间进行排序
     * @tparam T
     * @param arr
     * @param l
     * @param r
     */
    template <typename T>
    void __mergeSort(T arr[],int l,int r){
        if (l >= r) return;

        int mid = (l + r) / 2;
        __mergeSort(arr,l,mid);
        __mergeSort(arr,mid + 1,r);
        __merge(arr,l,mid,r);
    }

    /**
     * 归并排序 对arr [0,endIndex] 进行归并排序
     * @tparam T
     * @param arr
     * @param beginIndex 数组起始下标
     * @param endIndex 数组结束下标
     */
    template <typename T>
    void mergeSort(T arr[],int endIndex){
        __mergeSort(arr,0,endIndex);
    }


    /*********************************优化版本***********************************/
    /**
     * 优化点
     * 1：由于归并排序在合并时，左右两边已经排好序，因此如果此时中间mid元素也就是左边最大一个元素小于mid+1也就是右边第一个元素，则没必要在继续归并，因为已经是排好序的。
     * 2：在归并排序时，如果此时元素个数很小，则可以采用插入排序，性能会更优，因为数量小重复元素会比较多，插入排序有优势
     */
    template <typename T>
    void __mergeSortOpt(T arr[],int l,int r){
        if (l >= r)return;

        int mid = (l + r) / 2;
        __mergeSort(arr,l,mid);
        __mergeSort(arr,mid + 1,r);
        // 优化点1
        if (arr[mid] > arr[mid + 1])
            __merge(arr,l,mid,r);
    }
    /**
     * 归并排序优化 对 arr[0,endIndex] 进行归并排序
     * @tparam T
     * @param arr
     * @param endIndex
     */
    template <typename T>
    void mergeSortOpt(T arr[],int endIndex){
        __mergeSortOpt(arr,0,endIndex);
    }


    template <typename T>
    void __mergeSortOptWithInsert(T arr[],int l,int r){
        // 优化点2
        if (r - l <= 60){
            InsertionSort::insertionSortOpt(arr,r - l + 1);
            return;
        }

        int mid = (l + r) / 2;
        __mergeSort(arr,l,mid);
        __mergeSort(arr,mid + 1,r);
        // 优化点1
        if (arr[mid] > arr[mid + 1])
            __merge(arr,l,mid,r);
    }


    /**
     * 归并排序优化 对 arr[0,endIndex] 进行归并排序
     * @tparam T
     * @param arr
     * @param endIndex
     */
    template <typename T>
    void mergeSortOptWithInsert(T arr[],int endIndex){
        __mergeSortOptWithInsert(arr,0,endIndex);
    }




};


#endif //MERGESORT_MERGESORT_H
